import random


class MergeSort:
    """
    归并排序类，包括自顶向下归并排序和自底向上归并排序算法的实现。
    """

    @staticmethod
    def merge_sort_top_down(arr):
        """
        自顶向下归并排序算法的核心思想是将待排序的列表递归地划分为子列表，然后将子列表合并成有序的结果。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：自顶向下归并排序中，合并过程中相同元素的相对顺序不会改变。
        """
        def merge(left, right):
            """
            合并两个有序列表。

            参数：
            left (list): 左侧有序列表。
            right (list): 右侧有序列表。

            返回：
            list: 合并后的有序列表。
            """
            result = []
            i = j = 0

            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1

            # 步骤 4: 将剩余元素添加到结果列表
            result.extend(left[i:])
            result.extend(right[j:])
            return result

        if len(arr) <= 1:
            return arr

        # 步骤 1: 递归划分为子列表
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        # 步骤 1a: 对左侧子列表进行递归排序
        left = MergeSort.merge_sort_top_down(left)

        # 步骤 1b: 对右侧子列表进行递归排序
        right = MergeSort.merge_sort_top_down(right)

        # 步骤 2: 合并子列表
        return merge(left, right)

    @staticmethod
    def merge_sort_bottom_up(arr):
        """
        自底向上归并排序算法的核心思想是将待排序的列表划分为多个小的子列表，然后依次两两合并，直到得到有序的结果。

        参数：
        arr (list): 待排序的列表。

        返回：
        list: 排序后的列表。

        稳定性：
        是稳定排序算法。
        原因：自底向上归并排序中，合并过程中相同元素的相对顺序不会改变。
        """
        def merge(left, right):
            """
            合并两个有序列表。

            参数：
            left (list): 左侧有序列表。
            right (list): 右侧有序列表。

            返回：
            list: 合并后的有序列表。
            """
            result = []
            i = j = 0

            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1

            # 步骤 4: 将剩余元素添加到结果列表
            result.extend(left[i:])
            result.extend(right[j:])
            return result

        if len(arr) <= 1:
            return arr

        n = len(arr)
        step = 1

        # 步骤 1: 多次两两合并子列表
        while step < n:
            # 步骤 2: 遍历待合并的子列表
            for i in range(0, n - step, step * 2):
                left = arr[i:i + step]
                right = arr[i + step:i + step * 2]

                # 步骤 3: 合并子列表
                arr[i:i + step * 2] = merge(left, right)

            step *= 2

        return arr



# 主程序
if __name__ == "__main__":
    # 生成随机输入列表
    input_list = random.sample(range(1, 101), 10)
    print("随机输入列表:", input_list)

    # 创建 MergeSort 对象
    sorter = MergeSort()

    # 调用自顶向下归并排序方法进行排序
    sorted_list_top_down = sorter.merge_sort_top_down(input_list)
    # 输出结果
    print("自顶向下归并排序后的列表:", sorted_list_top_down)  # 自顶向下归并排序后的列表: [1, 2, 4, 5, 7]

    # 调用自底向上归并排序方法进行排序
    sorted_list_bottom_up = sorter.merge_sort_bottom_up(input_list)
    # 输出结果
    print("自底向上归并排序后的列表:", sorted_list_bottom_up)  # 自底向上归并排序后的列表: [1, 2, 4, 5, 7]
